{-
    Copyright © 2011 - 2021, Ingo Wechsung
 
    All rights reserved.
 
    Redistribution and use in source and binary forms, with or
    without modification, are permitted provided that the following
    conditions are met:

    -   Redistributions of source code must retain the above copyright
        notice, this list of conditions and the following disclaimer.

    -   Redistributions in binary form must reproduce the above
        copyright notice, this list of conditions and the following
        disclaimer in the documentation and/or other materials provided
        with the distribution. Neither the name of the copyright holder
        nor the names of its contributors may be used to endorse or
        promote products derived from this software without specific
        prior written permission.
 
    *THIS SOFTWARE IS PROVIDED BY THE
    COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
    IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
    WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
    USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
    AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
    IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
    THE POSSIBILITY OF SUCH DAMAGE.*
-}

{--

    This package provides common list functions for the Frege language.

    It contains all functions described in chapter 20 "Data.List" of the 
    _Haskell 2010 Language Report_. Where possible, the code has been ported
    from public Haskell source code 
    (http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.html).

 -}




package Data.List 
    inline (sort,
            delete, insert, deleteFirstsBy, \\, union, intersect) where

--import frege.Prelude 
import frege.prelude.PreludeList public (intersperse)

-- 'intersperse' is in PreludeList, but if someone needs to export it from here ...
-- intersperse = PreludeList.intersperse

{--
    The 'maximumBy' function takes a comparison function and a list
    and returns the greatest element of the list by the comparison function.
    The list must be finite and non-empty.
    -}
-- maximumBy               :: ListSource c => (a -> a -> Ordering) -> c a -> a
maximumBy cmp xs        =  foldl1 maxBy xs
                        where
                           maxBy x y = case cmp x y of
                                       Gt -> x
                                       _  -> y

{--
    The 'minimumBy' function takes a comparison function and a list
    and returns the least element of the list by the comparison function.
    The list must be finite and non-empty.
    -}
-- minimumBy               :: ListSource c => (a -> a -> Ordering) -> c a -> a
minimumBy cmp xs        =  foldl1 minBy xs
                        where
                           minBy x y = case cmp x y of
                                       Gt -> y
                                       _  -> x


{--
   The 'unfoldr' function is a dual to 'foldr': while 'foldr'
   reduces a list to a summary value, 'unfoldr' builds a list from
   a seed value.  The function takes the element and returns 'Nothing'
   if it is done producing the list or returns 'Just' @(a,b)@, in which
   case, @a@ is a prepended to the list and @b@ is used as the next
   element in a recursive call.  For example,

   > iterate f == unfoldr (\x -> Just (x, f x))

   In some cases, 'unfoldr' can undo a 'foldr' operation:

   > unfoldr f' (foldr f z xs) == xs

   if the following holds:

   > f' (f x y) = Just (x,y)
   > f' z       = Nothing

   A simple use of unfoldr:

   > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
   >  [10,9,8,7,6,5,4,3,2,1]
-}
unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
    case f b of
        Just (a,new_b) -> a : unfoldr f new_b
        Nothing        -> []

{--
    The 'inits' function returns all initial segments of the argument,
    shortest first.  For example,

    > inits "abc" == ["","a","ab","abc"]
    -}
-- inits                   :: [a] -> [[a]]
inits (x:xs)            =  [[]] ++ map (x:) (inits xs)
inits _                 =  [[]]
    

{--
    The 'tails' function returns all final segments of the argument,
    longest first.  For example,

    > tails "abc" == ["abc", "bc", "c",""]
    -}
tails (xxs@(_:xs))      =  xxs : tails xs
tails _                 =  [[]]

{--
    @takeUntil p xs@ is the same as @takeWhile (not • p) xs@
    -}
takeUntil p (x:xs) = if p x then [] else x:takeUntil p xs
takeUntil p _      = []


{--
    @dropUntil p xs@ is the same as @dropWhile (not • p) xs@

    Consequently, for all lists /xs/
    > takeUntil p xs ++ dropUntil p xs == xs
    -}
dropUntil p (list@(x:xs)) = if p x then list else dropUntil p xs
dropUntil p _             = []
    
{--
    @group xs@ returns a list of sub-lists made of adjacent equal elements in @xs@.
    All sublist are not empty and their concatenation yields again @xs@.
    -}
group (x:xs) = (x:ys) : group zs where (!ys,!zs) = span (x==) xs
group _ = []

{--
    @groupBy f xs@ groups by function @f@ instead of (==) that is used by @group@
    -}
groupBy f (x:xs) = (x:ys) : groupBy f zs where (!ys,!zs) = span (x `f`) xs
groupBy f _      = []

--- @elemBy f@ is a more general version of 'elem' that uses /f/ instead of '=='.
--- See also: 'using'
elemBy f e []    = false
elemBy f e (h:t) = if e `f` h then true else elemBy f e t

--- lookup a key in an association list
lookup key ((a,b):as)
    | key == a  = Just b
    | otherwise = lookup key as
lookup key []   = Nothing

{--
    'delete' @x@ removes the first occurrence of @x@ from its list argument. 
    For example,
    
    > delete ’a’ "banana" == "bnana"

    It is a special case of 'deleteBy', which allows the programmer to supply their own equality test.
    
    -}
delete =  deleteBy (==)

--- The 'deleteBy' function behaves like 'delete', but takes a user-supplied equality predicate.
deleteBy eq x []        = []
deleteBy eq x (y:ys)    = if x `eq` y then ys else y : deleteBy eq x ys

{--
    The 'deleteFirstsBy' function takes a predicate and two lists and
    returns the first list with the first occurrence of each element of
    the second list removed.
    -}
deleteFirstsBy eq       =  fold (flip (deleteBy eq))


{-
    The 'insert' function takes an element and a list and inserts the
    element into the list at the last position where it is still less
    than or equal to the next element.  In particular, if the list
    is sorted before the call, the result will also be sorted.
    It is a special case of 'insertBy', which allows the programmer to
    supply their own comparison function.
    -}
insert :: Ord a => a -> [a] -> [a]
insert e ls = insertBy (<=>) e ls

--- The non-overloaded version of 'insert'.
insertBy cmp x [] = [x]
insertBy cmp x (ys@y:ys') = case  x `cmp` y of 
     Gt ->  y : insertBy cmp x ys'
     _  ->  x : ys

infix  14 `\\`
{--
    The '\\' function is list difference (non-associative).
    In the result of @xs@ '\\' @ys@, the first occurrence of each element of
    @ys@ in turn (if any) has been removed from @xs@.  Thus

    > (xs ++ ys) \\ xs == ys.
    
    It is a special case of 'deleteFirstsBy', which allows the programmer
    to supply their own equality test.
    -}
(\\)                    :: (Eq a) => [a] -> [a] -> [a]
(\\)                    =  fold (flip delete)

{--
    The 'union' function returns the list union of the two lists.
    For example,
    
    > "dog" `union` "cow" == "dogcw"

    Duplicates, and elements of the first list, are removed from the
    the second list, but if the first list contains duplicates, so will
    the result.
    
    It is a special case of 'unionBy', which allows the programmer to supply
    their own equality test.
    -}
union            :: (Eq a) => [a] -> [a] -> [a]
union            = unionBy (==)

--- The 'unionBy' function is the non-overloaded version of 'union'.
unionBy eq xs ys        =  xs ++ fold (flip (deleteBy eq)) (uniqueBy eq ys) xs

{--
    The 'intersect' function takes the list intersection of two lists.
    For example,

    > [1,2,3,4] `intersect` [2,4,6,8] == [2,4]

    If the first list contains duplicates, so will the result.

    > [1,2,2,3,4] `intersect` [6,4,4,2] == [2,2,4]

    It is a special case of 'intersectBy', which allows the programmer to
    supply their own equality test.
    -}
intersect               :: (Eq a) => [a] -> [a] -> [a]
intersect               =  intersectBy (==)

--- The 'intersectBy' function is the non-overloaded version of 'intersect'.
intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]

{--
    'unique' removes duplicate elements from an unsorted list,
    which may or may not be faster than using @(uniq • sort)@
    
    This function is known as @nub@ in Haskell and Prelude provides this as alias.

    However, the following holds
    > sort (unique xs) == uniq (sort xs)
 -}
unique (e:es) = e : unique (filter (e !=) es)
unique _ = []

nub = unique
nubBy = uniqueBy    

{--
    @uniqueBy f@ is a more general form of 'unique',
    but uses @f@ instead of '==' to decide
    whether equal elements are contained in the list.

    The following holds:
    > sortBy (comparing f) (uniqueBy (using f) xs) == uniqBy (using f) (sortBy (comparing f) xs)
    -}
uniqueBy f (e:es) = e : uniqueBy f (filter (not • f e) es)
uniqueBy f _      = []

{--
    'uniq' removes adjacent equal elements from a list
    > uniq [1, 2, 2, 3, 2] = [1, 2, 3, 2]
    This is most useful on sorted lists to remove duplicates.
    For unsorted lists use 'unique'
    -}
uniq (x:xs) = x : uniq (dropWhile (x==) xs)
uniq _ = []

{--
    @uniqBy f@ is a variant of 'uniq' that uses _f_ instead of '=='.
    In the result, there are no two adjacent elements _x_ and _y_ where
    the relation @y `f` x@ holds.

    This is most useful on sorted lists with projection functions that
    compare parts of the value for equality. See also 'using'.

    > uniqBy (using fst) [(1, 1), (2, 2), (2, 3), (3, 4), (2, 5)]
    >   = uniqBy (\a\b -> fst a == fst b) [(1, 1), (2, 2), (2, 3), (3, 4), (2, 5)]
    >   = [(1, 1), (2, 2), (3, 4), (2, 5)]

    The example shows that the first of adjacent, equal comparing elements is retained.
 -}
uniqBy eq (x:xs) = x : uniqBy eq (dropWhile (eq x) xs)
uniqBy eq _      = []

{--
    @partitioned p xs@ splits _xs_ in 2 lists and returns them as a tuple @(xs1, xs2)@,
    such that  _xs1_
    contains all elements of _xs_ that satisfy predicate _p_ and _xs2_ contains
    those that do not.

    The order of the elements of _xs_ is reversed in the results.
    The argument must be finite, it is processed in a tail recursive loop.
    
    See also 'partition', which is lazy and works on infinite lists, but may be slower
    on finite lists because it processes the argument twice.

    The following is true for all finite lists xs
    > let ps = partitionR p xs
    > in    all p (fst ps)
    >    && (not • any p) (snd ps)
    >    && length (fst ps) + length (snd ps) == length xs
    >    && all (`elem` xs) (fst ps)
    >    && all (`elem` xs) (snd ps)
    >    && all (\x -> x `elem` fst ps || x `elem` snd ps) xs
    -}
partitioned p lst = loop lst [] [] where
    loop (x:xs) as bs
        | p x         = loop xs (x:as) bs
        | otherwise   = loop xs as (x:bs)
    loop _     as bs = (as,bs)

{--
     A variant of 'partition' that satisfies the Haskell 2010 specification.
    When the order of the results is irrelevant or one actually wants the results reversed, 
    consider the more efficient 'partitioned'.
    -}     
partition p lst = (filter p lst, filter (not • p) lst)

{--
    @intercalate xs xss@ is equivalent to @concat (intersperse xs xss)@    
    -}
intercalate ∷ [a] → [[a]] → [a]
intercalate xs xss = concat (intersperse xs xss)

--- 'zip4' zips 4 lists in the same way as 'zip' does it.
zip4 (a:as) (b:bs) (c:cs) (d:ds) = (a,b,c,d):zip4 as bs cs ds
zip4 _ _ _ _ = []

--- 'unzip4' unzips a list of quadrupels and returns a quadrupel of lists.
unzip4    =  foldr (\(a,b,c,d) \(as,bs,cs,ds) -> (a:as,b:bs,c:cs,d:ds)) ([],[],[],[])


--- 'zipWith4' /f/ zips 4 lists with function /f/ instead of the standard '(,,,)' that is used by 'zip4'
zipWith4 f (a:as) (b:bs) (c:cs) (d:ds) = f a b c d:zipWith4 f as bs cs ds
zipWith4 f _ _ _ _ = []

--- 'zip5' zips 5 lists in the same way as 'zip' does it.
zip5 (a:as) (b:bs) (c:cs) (d:ds) (e:es) 
    = (a,b,c,d,e):zip5 as bs cs ds es
zip5 _ _ _ _ _ = []

--- 'unzip5' unzips a list of quintuples and returns a quintuple of lists.
unzip5    =  foldr (\(a,b,c,d,e) \(as,bs,cs,ds,es) 
                    -> (a:as,b:bs,c:cs,d:ds,e:es)) ([],[],[],[],[])

--- 'zipWith5' /f/ zips 5 lists with function /f/ instead of the standard '(,,,,)' that is used by 'zip5'
zipWith5 f (a:as) (b:bs) (c:cs) (d:ds) (e:es) 
    = f a b c d e:zipWith5 f as bs cs ds es
zipWith5 f _ _ _ _ _ = []

--- 'zip6' zips 6 lists in the same way as 'zip' does it.
zip6 (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
    = (a,b,c,d,e,f):zip6 as bs cs ds es fs
zip6 _ _ _ _ _ _  = []

--- 'unzip6' unzips a list of sextuples and returns a sextuple of lists.
unzip6    =  foldr (\(a,b,c,d,e,f) \(as,bs,cs,ds,es,fs) 
                  -> (a:as,b:bs,c:cs,d:ds,e:es,f:fs)) ([],[],[],[],[],[])

--- 'zipWith6' /f/ zips 6 lists with function /f/ instead of the standard '(,,,,,)' that is used by 'zip6'
zipWith6 h (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
    = h a b c d e f:zipWith6 h as bs cs ds es fs
zipWith6 h _ _ _ _ _ _ = []

--- 'zip7' zips 7 lists in the same way as 'zip' does it.
zip7 (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
    = (a,b,c,d,e,f,g):zip7 as bs cs ds es fs gs
zip7 _ _ _ _ _ _ _ = []

--- 'unzip7' unzips a list of septuples and returns a septuple of lists.
unzip7    =  foldr (\(a,b,c,d,e,f,g) \(as,bs,cs,ds,es,fs,gs) 
                  -> (a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs)) ([],[],[],[],[],[],[])

--- 'zipWith7' /f/ zips 7 lists with function /f/ instead of the standard '(,,,,,,)' that is used by 'zip7'
zipWith7 h (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
    = h a b c d e f g:zipWith7 h as bs cs ds es fs gs
zipWith7 h _ _ _ _ _ _ _ = []

{--
    @sortBy f xs@ is a stable sort (merge sort), it uses /f/ to decide the order of elements.
    If @a `f` b@ is 'Lt' or 'Eq', then /a/ comes before /b/, otherwise /b/ comes before /a/.

    see also 'comparing',  'descending'
-}
sortBy f as = sortBy' f (toList as) where
    sortBy' !by []  = []
    sortBy' !by [x] = [x]
    sortBy' !by (list@[a,b]) = if a `by` b == Gt then [b,a] else list
    sortBy' !by xs = merge by (sortBy' by l1) (sortBy' by l2)
        where
            (l1,l2) = splitted xs
            splitted [] = ([],[])
            splitted xs = (take n2 xs, drop n2 xs) where n2 = length xs `quot` 2

{-- 
    Merge two lists, taking elements from the left as long as
    they are not 'Gt' (according to the passed comparison function)
    than the head element from the right.
    
    Makes most sense when the lists are sorted by the same criteria.
    -}
merge !by [] x = x
merge !by (ass@a:as) (bss@b:bs) = case a `by` b of
    Gt -> b : merge by ass bs
    _  -> a : merge by as  bss
merge !by x _ = x

{-- 
    Standard sort uses operator '<=>' and demands that the type of 
    the list elements is an instance of 'Ord'
    -}
sort = sortBy (<=>)        


--- The 'transpose' function transposes the rows and columns of its argument.
--- For example,
--- > transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
transpose               :: [[a]] -> [[a]]
transpose ([]   : xss)   = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])
transpose []             = []

--- The 'subsequences' function returns the list of all subsequences of the argument.
--- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
-- subsequences            :: [a] -> [[a]]
subsequences xs         =  [] : nonEmptySubsequences xs

{--
    The 'nonEmptySubsequences' function returns the list of all subsequences 
    of the argument, except for the empty list.
    > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
    -}
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
    where f ys r = ys : (x : ys) : r
nonEmptySubsequences _       =  []

--- The 'permutations' function returns the list of all permutations of the argument.
--- > permutations "abc" == ["abc","bac","cba","bca","cab","acb"]
-- permutations            :: [a] -> [[a]]
permutations xs0  =  xs0 : perms xs0 [] where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f • (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

{-- 
    The 'mapAccumL' function behaves like a combination of 'map' and
    'fold'; it applies a function to each element of a list, passing
    an accumulating parameter from left to right, and returning a final
    value of this accumulator together with the new list.
    -}
mapAccumL ::  
          (acc -> x -> (acc, y)) -- Function of elt of input list
                                    -- and accumulator, returning new
                                    -- accumulator and elt of result list
          -> acc            -- Initial accumulator 
          -> [x]            -- Input list
          -> (acc, [y])     -- Final accumulator and result list
mapAccumL f s (x:xs)    =  (s'',y:ys)
                           where (s', y ) = f s x
                                 (s'',ys) = mapAccumL f s' xs
mapAccumL _ s []        =  (s, [])
{--
    The 'mapAccumR' function behaves like a combination of 'map' and
    'foldr'; it applies a function to each element of a list, passing
    an accumulating parameter from right to left, and returning a final
    value of this accumulator together with the new list.
    -}
mapAccumR :: 
             (acc -> x -> (acc, y))     -- Function of elt of input list
                                        -- and accumulator, returning new
                                        -- accumulator and elt of result list
            -> acc              -- Initial accumulator
            -> [x]              -- Input list
            -> (acc, [y])               -- Final accumulator and result list
mapAccumR f s (x:xs)    =  (s'', y:ys)
                           where (s'',y ) = f s' x
                                 (s', ys) = mapAccumR f s xs
mapAccumR _ s []        =  (s, [])
{--
    The 'stripPrefix' function drops the given prefix from a list.
    It returns 'Nothing' if the list did not start with the prefix
    given, or 'Just' the list after the prefix, if it does.

    > stripPrefix "foo" "foobar" -> Just "bar"
    > stripPrefix "foo" "foo" -> Just ""
    > stripPrefix "foo" "barfoo" -> Nothing
    > stripPrefix "foo" "barfoobaz" -> Nothing
    -}
stripPrefix [] ys = Just ys
stripPrefix (x:xs) (y:ys)
 | x == y = stripPrefix xs ys
stripPrefix _ _ = Nothing

{--
    The 'isPrefixOf' function takes two lists and returns @true@
    iff the first list is a prefix of the second.
    -}
isPrefixOf (x:xs) (y:ys) =  x == y && isPrefixOf xs ys
isPrefixOf []     _      =  true
isPrefixOf (_:_)  []     =  false

{--
    The 'isSuffixOf' function takes two lists and returns @true@
    iff the first list is a suffix of the second.
    Both lists must be finite.
    -}
isSuffixOf              :: (Eq a) => [a] -> [a] -> Bool
isSuffixOf x y          =  reverse x `isPrefixOf` reverse y

{--
    The 'isInfixOf' function takes two lists and returns @true@
    iff the first list is contained, wholly and intact,
    anywhere within the second.

    Example:

    > isInfixOf "Haskell" "I really like Haskell." == true
    > isInfixOf "Ial" "I really like Haskell." == false
-}
isInfixOf               :: (Eq a) => [a] -> [a] -> Bool
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)

{-- 
    The 'elemIndex' function returns the index of the first element
    in the given list which is equal (by '==') to the query element,
    or 'Nothing' if there is no such element.
-}
elemIndex       :: Eq a => a -> [a] -> Maybe Int
elemIndex x     = findIndex (x==)

{--
    The 'elemIndices' function extends 'elemIndex', by returning the
    indices of all elements equal to the query element, in ascending order.
    -}
elemIndices     :: Eq a => a -> [a] -> [Int]
elemIndices x   = findIndices (x==)

{--
    The 'find' function takes a predicate and a list and returns the
    first element in the list matching the predicate, or 'Nothing' if
    there is no such element.
    -}
find            :: (a -> Bool) -> [a] -> Maybe a
find p          = listToMaybe • filter p

{-- 
    The 'findIndex' function takes a predicate and a list and returns
    the index of the first element in the list satisfying the predicate,
    or 'Nothing' if there is no such element.
    -}
findIndex       :: (a -> Bool) -> [a] -> Maybe Int
findIndex p     = listToMaybe • findIndices p

{--
    The 'findIndices' function extends 'findIndex', by returning the
    indices of all elements satisfying the predicate, in ascending order.
-}
findIndices      :: (a -> Bool) -> [a] -> [Int]
findIndices p ls = loop 0 ls
     where
       loop _ [] = []
       loop n (x:xs) | p x       = n : loop (n + 1) xs
                     | otherwise = loop (n + 1) xs


{--
    The 'genericLength' function is an overloaded version of 'length'.  In
    particular, instead of returning an 'Int', it returns any type which is
    an instance of 'Num'.  It is, however, less efficient than 'length'.
    -}
genericLength           :: (Num i) => [b] -> i
genericLength xs        = genericLength xs zero where
    genericLength [] len     =  len
    genericLength (_:ys) len =  genericLength ys (one + len)


{--
    The 'genericTake' function is an overloaded version of 'take', which
    accepts any 'Integral' value as the number of elements to take.
    -}
genericTake             :: (Integral i) => i -> [a] -> [a]
genericTake n _ | n <= zero = []
genericTake _ []        =  []
genericTake n (x:xs)    =  x : genericTake (n-one) xs

{--
    The 'genericDrop' function is an overloaded version of 'drop', which
    accepts any 'Integral' value as the number of elements to drop.
    -}
genericDrop             :: (Integral i) => i -> [a] -> [a]
genericDrop n xs | n <= zero = xs
genericDrop _ []        =  []
genericDrop n (_:xs)    =  genericDrop (n-one) xs


{-- 
    The 'genericSplitAt' function is an overloaded version of 'splitAt', which
    accepts any 'Integral' value as the position at which to split.
    -}
genericSplitAt          :: (Integral i) => i -> [b] -> ([b],[b])
genericSplitAt n xs | n <= zero =  ([],xs)
genericSplitAt _ []     =  ([],[])
genericSplitAt n (x:xs) =  (x:xs',xs'') where
    (xs',xs'') = genericSplitAt (n-one) xs

{--
    The 'genericIndex' function is an overloaded version of '!!', which
    accepts any 'Integral' value as the index.
    -}
genericIndex :: (Integral a) => [b] -> a -> b
genericIndex (x:_) n | n == zero = x
genericIndex (_:xs) n
 | n > zero  = genericIndex xs (n-one)
 | otherwise = error "List.genericIndex: negative argument."
genericIndex _ _      = error "List.genericIndex: index too large."

{--
    The 'genericReplicate' function is an overloaded version of 'replicate',
    which accepts any 'Integral' value as the number of repetitions to make.
    -}
genericReplicate        :: (Integral i) => i -> a -> [a]
genericReplicate n x    =  genericTake n (repeat x)

